package master;

import java.lang.reflect.ParameterizedType;
import java.util.HashMap;
import java.util.Map;

/**
 * @author chenyw
 * @date 2022/8/20 18:09
 */
public class M146LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode next;
        DLinkedNode pre;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }
    private int size;
    private int capacity;
    DLinkedNode head,tail;
    Map<Integer,DLinkedNode>  map=new HashMap<>();

    public M146LRUCache(int capacity) {
        this.size=0;
        this.capacity=capacity;
        head=new DLinkedNode();
        tail=new DLinkedNode();
        //伪头结点,,伪尾节点, head,tail位置一直不变
        head.next=tail;
        tail.pre=head;
    }

    public int get(int key) {
        DLinkedNode node = map.get(key);
        if(node==null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    //添加元素
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        if(node==null){
            node=new DLinkedNode(key,value);
            map.put(key,node);
            addToHead(node);
            size++;
            if(size>capacity){
                DLinkedNode tail=removeTail();
                map.remove(tail.key);
                size--;
            }
        }
        else {
            node.value=value;
            moveToHead(node);
        }
    }


    //删除尾结点
    private DLinkedNode removeTail() {
        DLinkedNode res=tail.pre;
        removeNode(res);
        return res;
    }


    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    //增加到头部
    private void addToHead(DLinkedNode node) {
        node.next=head.next;
        head.next=node;
        node.pre=head;
        node.next.pre=node;
    }

    //删除
    private void removeNode(DLinkedNode node) {
        node.next.pre=node.pre;
        node.pre.next=node.next;
    }
}
